#ifndef MINQUEUE_H
#define MINQUEUE_H

#include <cstdlib>
#include <vector>
#include <iostream>

using namespace std;

template <class DT>
class MinQueue {
public:
	void enqueue (DT*, int);
	DT* dequeue ();
	bool isempty ();
	bool isroot ();
	MinQueue(): head(0) {}

	~MinQueue () {
		node* current = head;
		while (current) {
			node* thenext = current->next;
			delete current;
			current = thenext;
		}
		head = 0;
	}

private:
	struct node {
		node* next;
		DT* data;
		int key;
	
		node (): data(0), key(0), next(0) {}
		node (DT* d, int k): data(d), key(k), next(0) {}
	};

	/* head points to the first element, not head->next */
	node* head; 
};

/* MinQueue functions definition */
template<class DT>
void MinQueue<DT>::enqueue (DT* newele, int key) {
	if (key <= 0) {
		cout<<"Please do not insert a char with key=0"<<endl;
		exit(0);
	}
	
	node* newnode = new node(newele, key);
	node* cur = head;
	node* pre = head;
	
	/* insert to the head of the queue */
	if(isempty() || newnode->key <= cur->key) {
		newnode->next = cur;
		head = newnode;
		return;	
	} else {
		cur = cur->next;
	}
	
	/* insert to the middle of the queue */
	while (cur != 0) {
		if (newnode->key <= cur->key){
			newnode->next = cur;
			pre->next = newnode;
			return;
		} else {
			pre = cur;
			cur = cur->next;
		}
	}
	
	/* insert to the tail of the queue */
	pre->next = newnode;
	newnode->next = 0;
}

template<class DT>
DT* MinQueue<DT>::dequeue () {
	if (!isempty()) {
		DT* temp = head->data;
		head = head->next;
		return temp;
	} else {
		return 0;
	}
}

template<class DT>
bool MinQueue<DT>::isempty() {
	if (head==0)
		return true;
	else 
		return false;
}

template<class DT>
bool MinQueue<DT>::isroot() {
	if (head->next==0)
		return true;
	else
		return false;
}

#endif
